1. Technical Field
This invention relates in general to computer graphics display systems, and more particularly, to a method for clipping a line segment boundary-defined area against a limiting plane and to a related clipped extraneous edge deletion method, both for use in such systems wherein graphics figures are represented by polylines of data corresponding to line segment boundary-defined areas.
2. Definitions
The following terms and phrases are used herein in accordance with the following meanings:
1. Line Segment Boundary-Defined Area: any geometric configuration having a closed boundary defined by means of vertices and connecting straight line segments, e.g., convex, concave and self-intersecting polygons.
2. Polyline: a set of at least two vertices and connecting line segment(s) (i.e., a set comprising at least one vector); a line segment boundary-defined area is defined by at least one polyline.
3. Continuous/Discontinuous: continuous means read or generated in consecutive order, whether clockwise or counterclockwise; discontinuous means read or generated in a nonsequential manner, and includes line segments read or generated in inconsistent directions, i.e., clockwise and counterclockwise.
3. Description of Prior Art
Typically, figures or objects to be displayed in a computer graphics system are defined using such primitives as lines, characters and/or line segment boundary-defined areas, such as polygons. Of the geometric operations performed by such systems, clipping is among the most important. Clipping allows the graphics system to only display those portions of a primitive which lie within an operator defined viewing window or region. Thus, boundary-defined area or polygon clipping is a process whereby a closed surface extending beyond the border of some viewing window, whether two-dimensional or three-dimensional, is reduced to a surface which does not extend beyond said border. Essentially, the process involves clipping off those parts of the closed surface which lie outside the area defining the field of view, to thereby eliminate off screen or invisible portions of figures from the actual developed image.
Perhaps the most commonly referenced closed surface clipping process is the Sutherland-Hodgman algorithm. Sutherland and Hodgman's clipping algorithm uses a divide-and-conquer strategy by solving a series of simple and identical problems which, when combined, solve the overall problem. The process is described in U.S. Pat. No. 3,816,726, entitled "Computer Graphics Clipping System for Polygons." Textual treatment of the Sutherland-Hodgman algorithm is provided by J. D. Foley and A. Van Dam, in Fundamentals of Interactive Computer Graphics at pp. 451-455 (1982), which is incorporated herein by reference.
Briefly described, the Sutherland and Hodgman algorithm accepts as input a series of vertices representative of a polygon, clips the polygon against a viewing boundary and outputs another series of vertices defining the clipped polygon. The algorithm continuously "marches" around a polygon from an arbitrary starting/ending vertex, at each step examining the relationship between successive vertices and the viewing boundary, or more particularly, one plane of the viewing boundary.
The critical requirement of the Sutherland-Hodgman algorithm is that polygon vertices be submitted to the algorithm in a continuous manner until all vertices of the polygon are considered. The continuous manner requirement can be a serious restriction to a graphics system user in a large number of applications. Frequently, in industrial and mechanical design applications, e.g., where a physical part of some kind is being designed, the order in which the user specifies the boundaries of a defined area is random. This occurs most often when a part is being designed which is symmetrical about an axis, or axes, such that the user need only define a half or quarter of the image ultimately to be displayed with the balance being computer generated.
In view of this, and the fact that the Sutherland-Hodgman algorithm requires the continuous input of vertices data, three options exist, namely; (1) through the applications program, the user can be restricted to defining only continuous line segment boundary-defined areas; (2) intermediate processing can be inserted either at the host computer or the graphics system to rearrange discontinuously presented data into consecutive data; or (3) a different closed surface clipping algorithm capable of handling discontinuously presented data can be used. The first listed option obviously results in a user restricted system, while the first and second listed options would both adversely affect system performance. This leaves the third option to be pursued. Although believed preferable, alternate clipping algorithms capable of handling discontinuously presented data definitive of line segment boundary-defined areas typically require a relatively large amount of memory to store clipped points for subsequent sorting and generation of line segments therebetween. For example, the IBM 5080 is such a graphics system, requiring 1k of memory for implementation of its clipping algorithm. Thus, a nonrestrictive closed surface clipping method operable on continuously or discontinuously presented data and requiring less hardware and/or software to implement than presently available clipping methods capable of operating on such data, is believed clearly beneficial.
Another disadvantage of most line segment boundary-defined area clipping algorithms concerns the deletion of extraneously produced lines falsely representative of clipped boundaries, e.g., such lines are produced where the clipping process results in two disjoint polygons. The problem is believed to occur in most, if not all, known clipping algorithms, including the Sutherland-Hodgman method, and has been addressed by either removing the extraneous edges with more processing steps subsequent the clipping algorithm or by using a more complex clipping algorithm, such as the Weiler-Atherton algorithm discussed at p. 455 of the referenced Foley and Van Dam text, to initially avoid generating the clipped extraneous edges. Obviously, both of these approaches have an adverse effect on performance. Thus, a novel clipped extraneous edge deletion method as described below, which is more efficient in operation, and which cooperates with a line segment boundary-defined area clipping method to more efficiently produce a clipped closed surface is believed clearly desirable.